Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Курсова робота ( частина 2 )
На тему:
"Динамічні структури даних"
з дисципліни:
" Програмування"
Вибір індивідуального варіанту:
Вибір АТД: №= [(30) + (1994) + (105) ] % 4 + 1 = 2
Вибір номера завдання: №=[(07) + (1994) + (83) ] % 10 + 1 = 5.
АТД «Черга», Варіант 5.
ЗАВДАННЯ НА КУРСОВУ РОБОТУ
ЗАВДАННЯ 3.
Змоделювати абстрактний тип даних (АТД). Оформити АТД у вигляді класа. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
ЗАВДАННЯ 4.
У місті розташовано n автобусних зупинок, позначених числами з N={1,2,....,n}. В текстовому файлі записано k автобусних маршрутів, заданих послідовностями сусідніх зупинок при русі автобуса в одному напрямку:
М1={P11,P12,...,P1m1},
М2={P21,P22,...,P2m2},
.....
Mk={Pk1,Pk2,...,Pkmk}, де Pij натуральне число з N.
Написати програму, що по заданих номерах зупинок I і J визначає найбільш швидкий шлях переміщення пасажира з зупинки I у зупинку J з використанням наявних маршрутів автобусів при умові, що час руху між сусідніми зупинками у всіх маршрутах однаковий і у 3 рази менший за час зміни маршруту. Автобуси можуть рухатись в обох напрямках.
ЗМІСТ
1. ТЕОРЕТИЧНА ЧАСТИНА
2. ЗАВДАННЯ 3. ПОБУДОВА АТД
2.1. Постановка задачі
2.2. Динаміка вмісту
2.3. Результати виконання програми
3. ЗАВДАННЯ 4. ЗАСТОСУВАННЯ АТД
3.1. Постановка задачі
3.2. Алгоритм розв’язання задачі
3.2.1. Словесний опис алгоритму
3.2.2. Граф-схема алгоритму
3.3. Результати виконання програми
ВИСНОВКИ
СПИСОК ЛІТЕРАТУРИ
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3
ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 4
1. ТЕОРЕТИЧНА ЧАСТИНА
СТЕК
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов).
Найбільш наочним прикладом організації стека служить дитяча пірамідка, в якій додавання й зняття кілець здійснюється саме відповідно до визначення стека. Можна уявити також стопку тарілок. Нижня тарілка із цієї стопки буде використана останньою, а верхня тарілка, яка була покладена в стопку останньою, буде використана першою. Подібне відбувається й в стеку.
Стеки широко використовуються як для розв’язання прикладних задач, так і в системному програмному забезпеченні, включаючи компілятори і інтерпретатори.
Історично склалося так, що дві основні операції для стека - помістити в стек і вилучити зі стека - одержали назву відповідно "заштовхнути" і "виштовхнути". Тому для реалізації стека необхідно створити дві функції: "push" (заштовхнути), що поміщає елемент у вершину стека, і "pop" (виштовхнути), що вилучає з вершини стека один елемент. Необхідно також передбачити певну область у пам'яті, де фактично буде зберігатися стек. Для цього можна використати масив або можна виділити область пам'яті, використовуючи засоби динамічного розподілу пам'яті.
ЧЕРГА
ЧергоюFІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу.
Дек - особливий вид черги. Дек (від англ. deq - doubleendedqueue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців...
